package com.sheng.leetcode.year2023.month11.day10;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2023/11/10
 * <p>
 * 2300. 咒语和药水的成功对数<p>
 * <p>
 * 给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，<p>
 * 其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。<p>
 * 同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。<p>
 * 请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。<p>
 * <p>
 * 示例 1：<p>
 * 输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7<p>
 * 输出：[4,0,3]<p>
 * 解释：<p>
 * - 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。<p>
 * - 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。<p>
 * - 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。<p>
 * 所以返回 [4,0,3] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：spells = [3,1,2], potions = [8,5,8], success = 16<p>
 * 输出：[2,0,2]<p>
 * 解释：<p>
 * - 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。<p>
 * - 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。<p>
 * - 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。<p>
 * 所以返回 [2,0,2] 。<p>
 * <p>
 * 提示：<p>
 * n == spells.length<p>
 * m == potions.length<p>
 * 1 <= n, m <= 10^5<p>
 * 1 <= spells[i], potions[i] <= 10^5<p>
 * 1 <= success <= 10^10<p>
 */
public class LeetCode2300 {

    @Test
    public void test01() {
//        int[] spells = {5, 1, 3}, potions = {1, 2, 3, 4, 5};
//        long success = 7;
        int[] spells = {3, 1, 2}, potions = {8, 5, 8};
        long success = 16;
        System.out.println(Arrays.toString(new Solution().successfulPairs(spells, potions, success)));
    }
}

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length;
        int m = potions.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            // 排序后二分查找数组 potions
            int l = 0, r = m - 1;
            int mod = 0;
            while (l < r) {
                mod = (l + r) / 2;
                if ((long) spells[i] * potions[mod] >= success) {
                    r = mod;
                } else {
                    l = mod + 1;
                }
            }
            // 校验
            if ((long) spells[i] * potions[r] >= success) {
                ans[i] = m - r;
            }
        }
        return ans;
    }
}
